/*
 * @Author: 缄默
 * @Date: 2021-11-10 20:49:47
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-11 20:41:26
 */

//判断二叉树是二叉平衡树

#include <iostream>
#include <vector>
#include "../../DataStructure/tree.hpp"

using namespace std;

struct returnType {
    int height;
    bool isBalanced;
    returnType(int height1, bool isBalanced1) : height(height1), isBalanced(isBalanced1) { }
};

bool isBalancedTree(TreeNode* node);
returnType* process(TreeNode* head);

int main() {
    vector<int> preOrder({4, 2, 1, 0, 3, 6, 5, 7});
    vector<int> inOrder({0, 1, 2, 3, 4, 5, 6, 7});
    TreeNode* head = buildTree(preOrder, inOrder, 0, 0, preOrder.size() - 1);
    cout << isBalancedTree(head) << endl;
    return 0;
}

bool isBalancedTree(TreeNode* head) {
    return process(head)->isBalanced;
}

returnType* process(TreeNode* head) {
    if (head == nullptr) return new returnType(true, 0);
    returnType* leftData = process(head->left);
    returnType* rightData = process(head->right);
    int height = (leftData->height < rightData->height ? rightData->height : leftData->height) + 1; 
    bool balance = leftData->isBalanced && rightData->isBalanced && (abs(leftData->height - rightData->height) < 2);
    return new returnType(balance, height);
} 

